0
0.0

Jun 30, 2018
06/18

by
Eilon Solan

texts

######
eye 0

######
favorite 0

######
comment 0

We present a new tool for the study of multiplayer stochastic games, namely the modified game, which is a normal-form game that depends on the discount factor, the initial state, and for every player a partition of the set of states and a vector that assigns a real number to each element of the partition. We study properties of the modified game, like its equilibria, min-max value, and max-min value. We then show how this tool can be used to prove the existence of a uniform equilibrium in a...

Topics: Probability, Mathematics

Source: http://arxiv.org/abs/1703.04026

0
0.0

Jun 29, 2018
06/18

by
Eilon Solan

texts

######
eye 0

######
favorite 0

######
comment 0

This paper presents a new solution concept for multiplayer stochastic games, namely, acceptable strategy profiles. For each player $i$ and state $s$ in a stochastic game, let $w_i(s)$ be a real number. A strategy profile is \emph{$w$-acceptable}, where $w=(w_i(s))$, if the discounted payoff to each player $i$ at every initial state $s$ is at least $w_i(s)$, provided the discount factor of the players is sufficiently close to 1. Our goal is to provide simple strategy profiles that are...

Topics: Optimization and Control, Mathematics, Probability, Computing Research Repository, Computer Science...

Source: http://arxiv.org/abs/1608.05272

36
36

Sep 19, 2013
09/13

by
Rida Laraki; Eilon Solan

texts

######
eye 36

######
favorite 0

######
comment 0

We prove that every two-player non-zero-sum Dynkin game in continuous time admits an epsilon-equilibrium in randomized stopping times. We provide a condition that ensures the existence of an epsilon-equilibrium in non-randomized stopping times.

Source: http://arxiv.org/abs/1009.5627v1

29
29

Sep 18, 2013
09/13

by
Eilon Solan; Nicolas Vieille

texts

######
eye 29

######
favorite 0

######
comment 0

We study irreducible time-homogenous Markov chains with finite state space in discrete time. We obtain results on the sensitivity of the stationary distribution and other statistical quantities with respect to perturbations of the transition matrix. We define a new closeness relation between transition matrices, and use graph-theoretic techniques, in contrast with the matrix analysis techniques previously used.

Source: http://arxiv.org/abs/math/0306248v1

0
0.0

Jun 30, 2018
06/18

by
Eran Shmaya; Eilon Solan

texts

######
eye 0

######
favorite 0

######
comment 0

Two concepts of random stopping times in continuous time have been defined in the literature, mixed stopping times and randomized stopping times. We show that under weak conditions these two concepts are equivalent, and, in fact, that all types of random stopping times are equivalent. We exhibit the significance of the equivalence relation between stopping times using stopping problems and stopping games. As a by-product we extend Kuhn's Theorem to stopping games in continuous time.

Topics: Probability, Mathematics

Source: http://arxiv.org/abs/1403.7886

0
0.0

Jun 30, 2018
06/18

by
Cy Maor; Eilon Solan

texts

######
eye 0

######
favorite 0

######
comment 0

In repeated games, cooperation is possible in equilibrium only if players are sufficiently patient, and long-term gains from cooperation outweigh short-term gains from deviation. What happens if the players have incomplete information regarding each other's discount factors? In this paper we look at repeated games in which each player has incomplete information regarding the other player's discount factor, and ask when full cooperation can arise in equilibrium. We provide necessary and...

Topics: Probability, Quantitative Finance, Mathematics, Economics

Source: http://arxiv.org/abs/1411.1368

0
0.0

Jun 30, 2018
06/18

by
Asaf Cohen; Eilon Solan

texts

######
eye 0

######
favorite 0

######
comment 0

Bandit problems model the trade-off between exploration and exploitation in various decision problems. We study two-armed bandit problems in continuous time, where the risky arm can have two types: High or Low; both types yield stochastic payoffs generated by a Levy process. We show that the optimal strategy is a cut-off strategy and we provide an explicit expression for the cut-off and for the optimal payoff.

Topics: Probability, Mathematics

Source: http://arxiv.org/abs/1407.7241

36
36

Sep 22, 2013
09/13

by
Asaf Cohen; Eilon Solan

texts

######
eye 36

######
favorite 0

######
comment 0

We study two-armed Levy bandits in continuous-time, which have one safe arm that yields a constant payoff s, and one risky arm that can be either of type High or Low; both types yield stochastic payoffs generated by a Levy process. The expectation of the Levy process when the arm is High is greater than s, and lower than s if the arm is Low. The decision maker (DM) has to choose, at any given time t, the fraction of resource to be allocated to each arm over the time interval [t,t+dt). We show...

Source: http://arxiv.org/abs/0906.0835v1

43
43

Sep 18, 2013
09/13

by
Rida Laraki; Eilon Solan

texts

######
eye 43

######
favorite 0

######
comment 0

We study two-player zero-sum stopping games in continuous time and infinite horizon. We prove that the value in randomized stopping times exists as soon as the payoff processes are right-continuous. In particular, as opposed to existing literature, we do not assume any conditions on the relations between the payoff processes. We also show that both players have simple epsilon- optimal randomized stopping times; namely, randomized stopping times which are small perturbations of non-randomized...

Source: http://arxiv.org/abs/math/0306279v1

36
36

Sep 20, 2013
09/13

by
Eran Shmaya; Eilon Solan

texts

######
eye 36

######
favorite 0

######
comment 0

We prove that every two-player nonzero-sum stopping game in discrete time admits an \epsilon-equilibrium in randomized strategies for every \epsilon >0. We use a stochastic variation of Ramsey's theorem, which enables us to reduce the problem to that of studying properties of \epsilon-equilibria in a simple class of stochastic games with finite state space.

Source: http://arxiv.org/abs/math/0410173v1

34
34

Sep 21, 2013
09/13

by
Penelope Hernandez; Eilon Solan

texts

######
eye 34

######
favorite 0

######
comment 0

We study repeated games played by players with bounded computational power, where, in contrast to Abreu and Rubisntein (1988), the memory is costly. We prove a folk theorem: the limit set of equilibrium payoffs in mixed strategies, as the cost of memory goes to 0, includes the set of feasible and individually rational payoffs. This result stands in sharp contrast to Abreu and Rubisntein (1988), who proved that when memory is free, the set of equilibrium payoffs in repeated games played by...

Source: http://arxiv.org/abs/1008.2632v1

34
34

Sep 18, 2013
09/13

by
Dario Bauso; Ehud Lehrer; Eilon Solan

texts

######
eye 34

######
favorite 0

######
comment 0

We introduce the concept of attainable sets of payoffs in two-player repeated games with vector payoffs. A set of payoff vectors is called {\em attainable} if player 1 can ensure that there is a finite horizon $T$ such that after time $T$ the distance between the set and the cumulative payoff is arbitrarily small, regardless of what strategy player 2 is using. This paper focuses on the case where the attainable set consists of one payoff vector. In this case the vector is called an attainable...

Source: http://arxiv.org/abs/1201.6054v3

25
25

Sep 21, 2013
09/13

by
Jerome Renault; Eilon Solan; Nicolas Vieille

texts

######
eye 25

######
favorite 0

######
comment 0

We consider a dynamic version of sender-receiver games, where the sequence of states follows an irreducible Markov chain observed by the sender. Under mild assumptions, we provide a simple characterization of the limit set of equilibrium payoffs, as players become very patient. Under these assumptions, the limit set depends on the Markov chain only through its invariant measure. The (limit) equilibrium payoffs are the feasible payoffs that satisfy an individual rationality condition for the...

Source: http://arxiv.org/abs/1204.0323v1

0
0.0

Jun 30, 2018
06/18

by
Jerome Renault; Eilon Solan; Nicolas Vieille

texts

######
eye 0

######
favorite 0

######
comment 0

We study a dynamic model of information provision. A state of nature evolves according to a Markov chain. An informed advisor decides how much information to provide to an uninformed decision maker, so as to influence his short-term decisions. We deal with a stylized class of situations, in which the decision maker has a risky action and a safe action, and the payoff to the advisor only depends on the action chosen by the decision maker. The greedy disclosure policy is the policy which, at each...

Topics: Probability, Mathematics

Source: http://arxiv.org/abs/1407.5649

0
0.0

Jun 28, 2018
06/18

by
Ehud Lehrer; Eilon Solan; Omri N. Solan

texts

######
eye 0

######
favorite 0

######
comment 0

We provide a full characterization of the set of value functions of Markov decision processes.

Topics: Probability, Mathematics

Source: http://arxiv.org/abs/1511.02377

33
33

Jul 20, 2013
07/13

by
Dinah Rosenberg; Eilon Solan; Nicolas Vieille

texts

######
eye 33

######
favorite 0

######
comment 0

We study a class of two-player repeated games with incomplete information and informational externalities. In these games, two states are chosen at the outset, and players get private information on the pair, before engaging in repeated play. The payoff of each player only depends on his `own' state and on his own action. We study to what extent, and how, information can be exchanged in equilibrium. We prove that provided the private information of each player is valuable for the other player,...

Source: http://arxiv.org/abs/1007.4427v1

0
0.0

Jun 29, 2018
06/18

by
Lev Buhovsky; Eilon Solan; Omri Nisan Solan

texts

######
eye 0

######
favorite 0

######
comment 0

A set $A$ in a finite dimensional Euclidean space is \emph{monovex} if for every two points $x,y \in A$ there is a continuous path within the set that connects $x$ and $y$ and is monotone (nonincreasing or nondecreasing) in each coordinate. We prove that every open monovex set as well as every closed monovex set is contractible, and provide an example of a nonopen and nonclosed monovex set that is not contractible. Our proofs reveal additional properties of monovex sets.

Topics: General Topology, Mathematics

Source: http://arxiv.org/abs/1609.08844

32
32

Sep 18, 2013
09/13

by
Eilon Solan; Boris Tsirelson; Nicolas Vieille

texts

######
eye 32

######
favorite 0

######
comment 0

Three notions of random stopping times exist in the literature. We introduce two concepts of equivalence of random stopping times, motivated by optimal stopping problems and stopping games respectively. We prove that these two concepts coincide and that the three notions of random stopping times are equivalent.

Source: http://arxiv.org/abs/1211.5802v1

87
87

Jul 20, 2013
07/13

by
Marco Scarsini; Eilon Solan; Nicolas Vieille

texts

######
eye 87

######
favorite 0

######
comment 0

We consider a class of auctions (Lowest Unique Bid Auctions) that have achieved a considerable success on the Internet. Bids are made in cents (of euro) and every bidder can bid as many numbers as she wants. The lowest unique bid wins the auction. Every bid has a fixed cost, and once a participant makes a bid, she gets to know whether her bid was unique and whether it was the lowest unique. Information is updated in real time, but every bidder sees only what's relevant to the bids she made. We...

Source: http://arxiv.org/abs/1007.4264v1

23
23

Sep 21, 2013
09/13

by
Dinah Rosenberg; Eilon Solan; Nicolas Vieille

texts

######
eye 23

######
favorite 0

######
comment 0

Given an arbitrary long but finite sequence of observations from a finite set, we construct a simple process that approximates the sequence, in the sense that with high probability the empirical frequency, as well as the empirical one-step transitions along a realization from the approximating process, are close to that of the given sequence. We generalize the result to the case where the one-step transitions are required to be in given polyhedra.

Source: http://arxiv.org/abs/math/0508607v1

26
26

Sep 21, 2013
09/13

by
Ehud Lehrer; Eilon Solan; Yannick Viossat

texts

######
eye 26

######
favorite 0

######
comment 0

We study the structure of the set of equilibrium payoffs in finite games, both for Nash equilibrium and correlated equilibrium. A nonempty subset of R^2 is shown to be the set of Nash equilibrium payoffs of a bimatrix game if and only if it is a finite union of rectangles. Furthermore, we show that for any nonempty finite union of rectangles U and any polytope P in R^2 containing U, there exists a bimatrix game with U as set of Nash equilibrium payoffs and P as set of correlated equilibrium...

Source: http://arxiv.org/abs/0902.2770v1

30
30

Sep 21, 2013
09/13

by
Gadi Fibich; Arieh Gavious; Eilon Solan

texts

######
eye 30

######
favorite 0

######
comment 0

Typically, models with a heterogeneous property are considerably harder to analyze than the corresponding homogeneous models, in which the heterogeneous property is replaced with its average value. In this study we show that any outcome of a heterogeneous model that satisfies the two properties of differentiability and interchangibility is O(\epsilon^2) equivalent to the outcome of the corresponding homogeneous model, where \epsilon is the level of heterogeneity. We then use this averaging...

Source: http://arxiv.org/abs/1204.0813v1